inf = float('inf')
t = int(input())
for _ in range(t):
    n = int(input())
    board = [[0 for _ in range(n)] for _ in range(n)]
    for r in range(n):
        board[r] = list(map(int, input().split()))
    dp = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]  # dp[i][j][k] k 0->不放钱 1-> 放钱
    if not board[0][0] & 1:
        dp[0][0][0] = inf
        dp[0][0][1] = n
    else:
        dp[0][0][1] = inf

    for i in range(n):
        for j in range(n):
            if i == j == 0: continue
            min_cost = inf
            if board[i][j] & 1:  # 若为奇数可直接由上方或左方得到
                dp[i][j][1] = inf
                if i > 0:
                    min_cost = min(min_cost, min(dp[i - 1][j]))
                if j > 0:
                    min_cost = min(min_cost, dp[i][j - 1][0])
                dp[i][j][0] += min_cost
            else:  # 若为偶数 可由左边无代价得到 或者上方增加n代价得到
                dp[i][j][0] = inf
                if i > 0:
                    min_cost = min(min_cost, min(dp[i - 1][j]) + n)
                if j > 0:
                    min_cost = min(min_cost, dp[i][j - 1][1])
                dp[i][j][1] += min_cost
    if min(dp[-1][-1]) == inf:
        print("NO!")
    else:
        print(min(dp[-1][-1]))
